import java.util.ArrayList;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Stack;
import java.util.TreeSet;

/**
 * Greedy optimizer uses a greedy algorithm to try to find the optimum solution.
 * @author Yong Shin
 *
 */
public class GreedyOptimizer extends Optimizer {

	
	/**
	 * Calculate cost savings for all available split criteria at current node.
	 * 
	 * @param node current context tree node.
	 * @return PriorityQueue containing costs corresponding to each split criteria.
	 */
	private PriorityQueue<Cost> calculateCostSavings(ContextTreeNode node) {
		PriorityQueue<Cost> result = new PriorityQueue<Cost>();
		Iterator<SplitCriteria> iter = node.getAvailableCriteria().iterator();
		while (iter.hasNext()) {
			SplitCriteria criteria = iter.next();
			
			// get bit counts for split criteria
			BitCounts[] bcounts = node.getData().getBitCounts(criteria.getContextID(), criteria.getBucketID());
			
			// check if any of the hypothetical split child nodes is empty
			if (bcounts[0].oneBits + bcounts[0].zeroBits == 0 || 
					bcounts[1].oneBits + bcounts[1].zeroBits == 0) {
				// do not remove the split criteria, just ignore it. 
//				iter.remove();
				continue;
			}
			
			// create Cost object corresponding to the split criteria
			Cost cost = new Cost(node, criteria);
			cost.addBitCounts(0, bcounts[0]);
			cost.addBitCounts(1, bcounts[1]);
			
			if (FULLDEBUG) {
			    System.out.println("Criteria: " + criteria + ", Cost: " + cost); 
                        }
                        else if (DEBUG) {
                            if (cost.getSaving()  >10.0) 
			       System.out.println("Criteria: " + criteria + ", Cost: " 
                                + cost.toStringSummary());
                        }
			
			result.add(cost);
		}
		return result;
	}
	
	public GreedyOptimizer(String ccdFile) {
		super(ccdFile);
	}
	
	@Override
	public ContextTreeNode findOptimalContextTree(double threshold) {
		
		// construct list of all available split criteria (This doesn't take account of
		// number of bits on each side.)
		TreeSet<SplitCriteria> availableCriteria = 
			ContextDefinition.getContextDefinition().getAllSplitCriteria();

		TreeSet<SplitCriteria> unusedCriteria ; // keep track of all unused split criteria. 
		unusedCriteria = new TreeSet<SplitCriteria>();
	        unusedCriteria.addAll(availableCriteria);

		if (DEBUG) {
			System.out.println("Potential split criteria:");
                        int i = 0; 
                        for (SplitCriteria c: availableCriteria) {
                          System.out.println("(" + (i+1) + ") " + c);
                          i++;
                        }
                }
		
		// create a context tree node from the context data and available split criteria
		ContextTreeNode root = new ContextTreeNode(availableCriteria, contextData);


		if (FULLDEBUG) {
		    root.getData().computeAndPrintOptimalAdaptiveCostSolution();
		}
                else if (DEBUG) {
                    System.out.println("Optimal non-tree cost: " + root.getData().computeOptimalAdaptiveCost());
                }

		// perform all worthwhile splits
		Stack<ContextTreeNode> nodes = new Stack<ContextTreeNode>();
		nodes.push(root);
                
                double totalcost = 0.0; // find total cost of tree. 
		double splitcost = 0.0;
                double splitcostupper = 0.0;
		
		while (!nodes.isEmpty()) {
			
			// get next node
			ContextTreeNode node = nodes.pop();
			
			if (DEBUG) {
			    System.out.println("Overall node, totalbits=" + 
					       node.getData().getTotal() +
					       " #bitcounts=" + 
					       node.getData().size() +
					       " overalladaptive=" + 
					       node.getData().getTotal().getAdaptiveCost() +
					       "\n" +
					       " adaptivecost=" +
					       node.getData().getAdaptiveCost() + 
					       " entropy=" +
					       node.getData().getEntropy() +
					       " optnontree=" + 
					       node.getData().computeOptimalAdaptiveCost()
					       );
                            if (FULLDEBUG) 
                               node.getData().printBitDistributionStats();
			}

			// calculate cost-savings for all available split criteria
			PriorityQueue<Cost> queue = calculateCostSavings(node);
			
                        if (queue.size() ==0) {
                            if (DEBUG)
				System.out.println("No possible splits left for node containing "+ node.getCount());
                            totalcost += Cost.adaptiveCostEstimate(node.getCount());
                            continue;
                        }
			// split if the cost-savings is worthwhile
			Cost best = queue.remove();
			
			if (DEBUG) {
				System.out.println("Current best cost savings: " + best);
			}
			
			if (best.getSaving() >= threshold) {

				// split the node
			    unusedCriteria.remove(best.getSplitCriteria());
				node.split(best.getSplitCriteria());
				splitcost += best.splitCost();
				splitcostupper += best.splitCostUpperBound();
				if (DEBUG) {
					System.out.println("node split->");
					System.out.println(node);
				}
				
				// add child nodes to stack
				nodes.push(node.getLeftChild());
				nodes.push(node.getRightChild());
			}
                        else {
                            totalcost += Cost.adaptiveCostEstimate(node.getCount());
			}
			
		}
    
                System.out.println("Cost of tree: adaptive=" + totalcost + " split=" + splitcost
				   + " splitupper=" + splitcostupper + " total=" + (totalcost+splitcostupper));
		if (DEBUG) System.out.println("Unused split criteria:"+ unusedCriteria);

		                
		// dump the content of tree
		if (FULLDEBUG) {
		       System.out.println("Optimization tree->");
			dumpContextTree(root);
			}
		
		return root;
	}

}
